﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0059_FindMin : IAlgorithm
    {
        // 153. 寻找旋转排序数组中的最小值

        // 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
        //  若旋转 4 次，则可以得到[4, 5, 6, 7, 0, 1, 2]
        //  若旋转 7 次，则可以得到[0, 1, 2, 4, 5, 6, 7]
        // 注意，数组[a[0], a[1], a[2], ..., a[n - 1]] 旋转一次 的结果为数组[a[n - 1], a[0], a[1], a[2], ..., a[n - 2]] 。

        // 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

        // 提示：
        //  n == nums.length
        //  1 <= n <= 5000
        //  -5000 <= nums[i] <= 5000
        //  nums 中的所有整数 互不相同
        //  nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 2 ,1 };
            // 算法执行与打印
            Console.WriteLine(FindMin(nums));
        }

        // 算法
        // 0 , 1, 2
        // 2 , 0, 1
        public int FindMin(int[] nums)
        {
            int low = 0;
            int high = nums.Length - 1;
            while (low < high)
            {
                int pivot = low + (high - low) / 2;
                if (nums[pivot] < nums[high])
                {
                    high = pivot;
                }
                else
                {
                    low = pivot + 1;
                }
            }
            return nums[low];
        }
    }
}
